# -*- coding: utf-8 -*-
# @Time    : 2020/10/20 15:39
# @Author  : luyvlei
# @File    : KMeans.py

import numpy as np
import random
class KMeans(object):
    def __init__(self,n_clusters,random_state=0):
        self.n_clusters = n_clusters

    def get_dis(self,feature_1,feature_2):
        """
        获取l2范数作为距离
        :param feature_1:特征1
        :param feature_2:特征2
        :return:特征距离
        """
        return np.linalg.norm(feature_1 - feature_2, ord=2)

    def is_center_changed(self,center_1,center_2):
        """
        比较两个中心列表是否相等，用于判断Kmeans的终止条件
        :param center_1: 第一个中心列表
        :param center_2: 第二个中心列表
        :return:
        """
        for i in range(len(center_1)):
            if np.linalg.norm(center_1[i] - center_2[i], ord=2) > 1e-6:
                return True
        return False

    def fit(self,features):
        """
        训练Kmeans
        :param features:numpy格式的特征，shape为[个数，特征维度]
        :return:返回KMeans对象
        """
        # 特征点个数必须大于要聚类的个数，不然没法初始化聚类中心
        assert features.shape[0] > self.n_clusters

        # 特征维度和数量
        feature_dimension = features.shape[1]
        feature_counts = features.shape[0]

        # 随机在已只点中选择n个点作为初始中心，只有这一次的聚类中心是真实的特征点
        cluster_center_index_list = random.sample(range(0,feature_counts), self.n_clusters)

        # 聚类结果存放在list中
        cluster = [[] for i in range(self.n_clusters)]

        # 将初始中心存入cluster
        for idx,i in enumerate(cluster_center_index_list):
            cluster[idx].append(features[i,:])

        # 所有点都进行距离计算并加入聚类中心
        for i in range(feature_counts):
            closest = 999999999
            closest_idx = -1
            for j in range(self.n_clusters):
                dis = self.get_dis(features[i, :], features[cluster_center_index_list[j]])
                if dis < closest:
                    closest = dis
                    closest_idx = j

            # 加入到聚类中心
            cluster[closest_idx].append(features[i, :])

        # 重新选择聚类中心,这次以后的中心都是虚拟中心，由聚类中的特征点的均值求得
        cluster_centers = []
        for points in cluster:
            mean_point = np.zeros((feature_dimension,))
            for p in points:
                # 每个cluster重新出一共中心来，方法是取均值，存放到cluster_center_index_list中
                mean_point += p

            mean_point = mean_point/len(points)
            cluster_centers.append(mean_point)

        # 开始不断迭代，终止条件为聚类中心不再变化（已有数学证明Kmeans一定能终止）
        while True:
            cluster = [[] for i in range(self.n_clusters)]
            # 重新加入聚类中心
            for i in range(feature_counts):
                closest = 999999999
                closest_idx = -1
                for j in range(self.n_clusters):
                    dis = self.get_dis(features[i, :], cluster_centers[j])
                    if dis < closest:
                        closest = dis
                        closest_idx = j

                # 加入到聚类中心
                cluster[closest_idx].append(features[i, :])

            # 重新选择聚类中心,这次是虚拟中心
            last_cluster_center = cluster_centers.copy() #拷贝
            cluster_centers = [] #新的中心
            for points in cluster:
                mean_point = np.zeros((feature_dimension,))
                for p in points:
                    # 每个cluster重新出一共中心来，方法是取均值，存放到cluster_center_index_list中
                    mean_point += p

                mean_point = mean_point / len(points)
                cluster_centers.append(mean_point)

            if not self.is_center_changed(last_cluster_center,cluster_centers):
                self.cluster_centers = cluster_centers
                break

        # 计算每个feature的label
        labels_ = []
        for i in range(feature_counts):
            closest = 999999999
            closest_idx = -1
            for j in range(self.n_clusters):
                dis = self.get_dis(features[i, :], cluster_centers[j])
                if dis < closest:
                    closest = dis
                    closest_idx = j

            # 加入到聚类中心
            labels_.append(closest_idx)
        self.labels_ = np.array(labels_)
        return self

    def predict(self,features):
        cls = []
        for feature in features:
            closest = 999999999
            closest_idx = -1
            for i in range(self.n_clusters):
                dis = self.get_dis(np.array(feature), self.cluster_centers[i])
                if dis < closest:
                    closest = dis
                    closest_idx = i
            cls.append(closest_idx)
        return np.array(cls).astype(np.int32)
